﻿namespace AdvancedTraining.Lesson04;

public class SubMatrixMaxSum
{
    public static int MaxSum(int[][]? m)
    {
        if (m == null || m.Length == 0 || m[0].Length == 0) return 0;
        // O(N^2 * M)
        var row = m.Length;
        var column = m[0].Length;
        var max = int.MinValue;
        for (var i = 0; i < row; i++)
        {
            // i~j
            var s = new int[column];
            for (var j = i; j < row; j++)
            {
                for (var k = 0; k < column; k++) s[k] += m[j][k];
                max = Math.Max(max, MaxSubArray(s));
            }
        }

        return max;
    }

    public static int MaxSubArray(int[]? arr)
    {
        if (arr == null || arr.Length == 0) return 0;
        var max = int.MinValue;
        var cur = 0;
        foreach (var item in arr)
        {
            cur += item;
            max = Math.Max(max, cur);
            cur = cur < 0 ? 0 : cur;
        }

        return max;
    }

    // 本题测试链接 : https://leetcode-cn.com/problems/max-submatrix-lcci/
    public static int[] GetMaxSubMatrix(int[][] m)
    {
        var row = m.Length;
        var column = m[0].Length;
        var max = int.MinValue;
        var a = 0;
        var b = 0;
        var c = 0;
        var d = 0;
        for (var i = 0; i < row; i++)
        {
            var s = new int[column];
            for (var j = i; j < row; j++)
            {
                var cur = 0;
                var begin = 0;
                for (var k = 0; k < column; k++)
                {
                    s[k] += m[j][k];
                    cur += s[k];
                    if (max < cur)
                    {
                        max = cur;
                        a = i;
                        b = begin;
                        c = j;
                        d = k;
                    }

                    if (cur < 0)
                    {
                        cur = 0;
                        begin = k + 1;
                    }
                }
            }
        }

        return [a, b, c, d];
    }

    /// <summary>
    /// 运行SubMatrixMaxSum的测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("开始测试SubMatrixMaxSum...");

        // 测试用例1: 基本功能测试
        var matrix1 = new int[][]
        {
            new int[] { 1, -2, 3 },
            new int[] { -4, 5, -6 },
            new int[] { 7, -8, 9 }
        };

        Console.WriteLine("测试矩阵1:");
        foreach (var row in matrix1)
        {
            Console.WriteLine($"[{string.Join(", ", row)}]");
        }

        var result1 = MaxSum(matrix1);
        Console.WriteLine($"最大子矩阵和: {result1}");

        var result1Matrix = GetMaxSubMatrix(matrix1);
        Console.WriteLine($"最大子矩阵位置: [{string.Join(", ", result1Matrix)}]");

        // 测试用例2: 全正数矩阵
        var matrix2 = new int[][]
        {
            new int[] { 1, 2 },
            new int[] { 3, 4 }
        };

        Console.WriteLine("\n测试矩阵2:");
        foreach (var row in matrix2)
        {
            Console.WriteLine($"[{string.Join(", ", row)}]");
        }

        var result2 = MaxSum(matrix2);
        Console.WriteLine($"最大子矩阵和: {result2}");

        var result2Matrix = GetMaxSubMatrix(matrix2);
        Console.WriteLine($"最大子矩阵位置: [{string.Join(", ", result2Matrix)}]");

        // 测试用例3: 全负数矩阵
        var matrix3 = new int[][]
        {
            new int[] { -1, -2 },
            new int[] { -3, -4 }
        };

        Console.WriteLine("\n测试矩阵3:");
        foreach (var row in matrix3)
        {
            Console.WriteLine($"[{string.Join(", ", row)}]");
        }

        var result3 = MaxSum(matrix3);
        Console.WriteLine($"最大子矩阵和: {result3}");

        var result3Matrix = GetMaxSubMatrix(matrix3);
        Console.WriteLine($"最大子矩阵位置: [{string.Join(", ", result3Matrix)}]");

        // 测试用例4: 单行矩阵
        var matrix4 = new int[][]
        {
            new int[] { -1, 2, 3, -4, 5 }
        };

        Console.WriteLine("\n测试矩阵4:");
        foreach (var row in matrix4)
        {
            Console.WriteLine($"[{string.Join(", ", row)}]");
        }

        var result4 = MaxSum(matrix4);
        Console.WriteLine($"最大子矩阵和: {result4}");

        var result4Matrix = GetMaxSubMatrix(matrix4);
        Console.WriteLine($"最大子矩阵位置: [{string.Join(", ", result4Matrix)}]");

        // 测试用例5: 单列矩阵
        var matrix5 = new int[][]
        {
            new int[] { 1 },
            new int[] { -2 },
            new int[] { 3 }
        };

        Console.WriteLine("\n测试矩阵5:");
        foreach (var row in matrix5)
        {
            Console.WriteLine($"[{string.Join(", ", row)}]");
        }

        var result5 = MaxSum(matrix5);
        Console.WriteLine($"最大子矩阵和: {result5}");

        var result5Matrix = GetMaxSubMatrix(matrix5);
        Console.WriteLine($"最大子矩阵位置: [{string.Join(", ", result5Matrix)}]");

        Console.WriteLine("\nSubMatrixMaxSum测试完成！");
    }
}